#include <stdio.h>
#include <stdlib.h>
//中缀表达式转后缀表达式 
#define MAXSIZE 100
typedef char ElemType;
//顺序栈声明
typedef struct 
{
    ElemType *data;
    int top;
}Stack;
//初始化
Stack *initstack()
{
    Stack *s=(Stack *)malloc(sizeof(Stack));
    s->data=(ElemType *)malloc(sizeof(Stack));
    s->top=0;   //因为要放一个0优先级的元素
    return s;
}
//全局变量
char expr[]="x/(i-j)*y";
//枚举常量
typedef enum
{
    Left_pare,Right_pare,add,sub,mul,Div,mod,eos,num
    //Div大写是因为div和其他函数名重了
}contentType;
//入栈
int push(Stack *s,ElemType n)
{
    if(s->top>=MAXSIZE-1)
    {
        printf("栈满了\n");
        return 0;
    }
    s->top++;
    s->data[s->top]=n;
    return 1;
}
//出栈
int pop(Stack *s,ElemType *n)
{
    if(s->top==0)
    {
        printf("空栈\n");
        return 0;
    }
    *n=s->data[s->top];
    s->top--;
    return 1;
}
//辨认每个字符的类型
contentType getToken(char *symbol,int *i)
{
    *symbol=expr[*i];
    (*i)++;
    switch(*symbol)
    {
        case '(':
        return Left_pare;
        case ')':
        return Right_pare;
        case '+':
        return add;
        case '-':
        return sub;
        case '*':
        return mul;
        case '/':
        return Div;
        case '%':
        return mod;
        case '\0':
        return eos;
        default:
        return num;
    }
}
contentType gettoken(ElemType symbol)
{
    switch(symbol)
    {
        case '(':
        return Left_pare;
        case ')':
        return Right_pare;
        case '+':
        return add;
        case '-':
        return sub;
        case '*':
        return mul;
        case '/':
        return Div;
        case '%':
        return mod;
        case '\0':
        return eos;
        default:
        return num;
    }
}
//转换
void become_RPV(Stack *s)
{
    int in_stack[]={0,19,12,12,13,13,13,0};    //栈里优先级
    int out_stack[]={20,19,12,12,13,13,13,0};  //栈外优先级
    //跟枚举常量一一对应，下标用枚举常量里的元素表示
    s->data[0]=eos;  //优先级为0的元素
    char symbol;
    int i=0;     //为了遍历字符数组
    contentType token;
    token=getToken(&symbol,&i);
    char e=0;   //为了打印出栈元素
    while(token!=eos)
    {
        if(token==num)
        {
            printf("%c",symbol);
        }
        else if(token==Right_pare)
        {
            pop(s,&e);
            while(e!='(')  //注意这里e的类型是字符变量
            {
                printf("%c",e);
                pop(s,&e);
            }
        }
        else
        {
            //如果栈外元素的优先级小于等于栈顶元素优先级，那么就一直出栈
            //直到栈外元素优先级大于栈顶元素优先级，那么栈外元素入栈
            while(in_stack[gettoken(s->data[s->top])]>=out_stack[token])
            {
                pop(s,&e);
                printf("%c",e);
            }
            push(s,symbol);
        }
        token=getToken(&symbol,&i);
    }
    while(s->data[s->top]!=eos)
    {
        pop(s,&e);
        printf("%c",e);
    }
}
int main()
{
    Stack *s=initstack();
    printf("%s\n",expr); //打印一下中缀表达式
    //转成后缀表达式
    become_RPV(s);
    return 0;
}
//输出：
//    x/(i-j)*y
//    xij-/y*